from typing import *
from math import inf


class Solution:

    def minimizeConcatenatedLength(self, words: List[str]) -> int:
        dp = [[inf] * 26 for _ in range(26)]

        def f(c):
            return ord(c) - ord('a')

        word = words[0]

        dp[f(word[0])][f(word[-1])] = len(word)

        for word in words[1::]:
            dp1 = [[inf] * 26 for _ in range(26)]
            s, e = f(word[0]), f(word[-1])
            for i in range(26):
                for j in range(26):
                    if dp[i][j] != inf:
                        dp1[i][e] = min(
                            dp1[i][e],
                            dp[i][j] + len(word) - (1 if j == s else 0))
                        dp1[s][j] = min(
                            dp1[s][j],
                            dp[i][j] + len(word) - (1 if e == i else 0))
            dp = dp1
        return min(min(v) for v in dp)


s = Solution()
print(s.minimizeConcatenatedLength(["aa", "ab", "bc"]))
print(s.minimizeConcatenatedLength(["aaa", "c", "aba"]))
# print(ord())